//
// Created by liushuai on 2021/2/2.
//

#include "search.h"

int findMinIndex(int* num,int n) {
    if (n<=0)
        return -1;
    int start = 0;
    int end = n - 1;
    while (start < end) {
        int mid = (end - start) / 2 + start;
        if (num[mid] < num[end])
            end = mid;
        else
            start = mid + 1;
    }
    return start;
}
int binarySearch(int* num,int start,int end,int target){
    while(start<end){
        int mid = (end-start)/2+start;
        if(num[mid] > target)
            end = mid-1;
        else
            start = mid+1;
    }
    return start;
}

int search(int* num, int n, int target) {
    if(n<=0)
        return -1;
    else{
        int rotate = findMinIndex(num,n);
        int start = 0;
        int end = n-1;

        if (num[end] >= num[rotate]) {
            return binarySearch(num,rotate,end,target);
        } else
            return binarySearch(num,start,rotate-1,target);
    }
}